//
// Created by 86138 on 2025/6/9.
//
#include <iostream>
#include "../01-intro/c1-1.h"

using namespace std;

namespace sweetcookie3 {

    typedef struct PNode {
        double coef;
        int expn;
        struct PNode *next;
    } PNode;

    typedef PNode* Polynomial;

    // 创建多项式节点
    PNode* CreateNode(double coef, int expn) {
        PNode* node = (PNode*)malloc(sizeof(PNode));
        if (!node) exit(OVERFLOW);
        node->coef = coef;
        node->expn = expn;
        node->next = NULL;
        return node;
    }

    // 将节点按指数升序插入多项式
    void InsertNode(Polynomial &P, PNode *node) {
        if (!node) return;

        PNode *pre = NULL, *current = P;

        // 寻找插入位置
        while (current && current->expn < node->expn) {
            pre = current;
            current = current->next;
        }

        // 处理相同指数项或插入新节点
        if (current && current->expn == node->expn) {
            current->coef += node->coef;  // 系数相加
            free(node);           // 释放临时节点
            if (current->coef == 0) {     // 如果系数为0，删除该节点
                if (pre) pre->next = current->next;
                else P = current->next;
                free(current);
            }
        } else {
            node->next = current;
            if (pre) pre->next = node;
            else P = node;
        }
    }

    // 多项式相加，结果存入Pa，销毁Pb
    void AddPolynomial(Polynomial &Pa, Polynomial &Pb) {
        PNode *pa = Pa, *pb = Pb;
        PNode *prePa = NULL;  // Pa的前驱指针
        Pb = NULL;           // 提前置空Pb，防止误用

        while (pa && pb) {
            if (pa->expn < pb->expn) {
                prePa = pa;
                pa = pa->next;
            }
            else if (pa->expn > pb->expn) {
                // 从Pb中取出节点插入Pa
                PNode *tmp = pb;
                pb = pb->next;

                tmp->next = pa;
                if (prePa) prePa->next = tmp;
                else Pa = tmp;

                prePa = tmp;
            }
            else {
                // 指数相同，系数相加
                pa->coef += pb->coef;
                PNode *tmp = pb;
                pb = pb->next;

                if (pa->coef == 0) {
                    // 系数为0，删除Pa中的节点
                    if (prePa) prePa->next = pa->next;
                    else Pa = pa->next;

                    free(pa);
                    pa = prePa ? prePa->next : Pa;
                } else {
                    prePa = pa;
                    pa = pa->next;
                }
                free(tmp);
            }
        }

        // 如果Pb还有剩余节点，全部接到Pa后面
        if (pb) {
            if (prePa) prePa->next = pb;
            else Pa = pb;
        }

        // Pb已经被处理完毕，置NULL
        Pb = NULL;
    }

    // 打印多项式
    void PrintPolynomial(Polynomial P) {
        PNode *p = P;
        int isFirst = 1;

        while (p) {
            if (!isFirst && p->coef > 0) printf("+");

            if (p->expn == 0) {
                printf("%.2f", p->coef);
            } else {
                printf("%.2fx^%d", p->coef, p->expn);
            }

            isFirst = 0;
            p = p->next;
        }

        if (isFirst) printf("0");  // 空多项式
        printf("\n");
    }

    // 销毁多项式
    void DestroyPolynomial(Polynomial *P) {
        PNode *p = *P, *tmp;
        while (p) {
            tmp = p;
            p = p->next;
            free(tmp);
        }
        *P = NULL;
    }
}

//using namespace sweetcookie3;

//int main() {
//    system("chcp 65001");
//
//    // 示例用法
//    Polynomial Pa = NULL, Pb = NULL;
//
//    // 创建多项式 Pa = 3x^2 + 2x + 1
//    InsertNode(Pa, CreateNode(3, 2));
//    InsertNode(Pa, CreateNode(2, 1));
//    InsertNode(Pa, CreateNode(1, 0));
//
//    // 创建多项式 Pb = 4x^3 - 2x^2 + 5
//    InsertNode(Pb, CreateNode(4, 3));
//    InsertNode(Pb, CreateNode(-2, 2));
//    InsertNode(Pb, CreateNode(5, 0));
//
//    printf("Pa: ");
//    PrintPolynomial(Pa);
//    printf("Pb: ");
//    PrintPolynomial(Pb);
//
//    AddPolynomial(Pa, Pb);
//    printf("After addition:\n");
//    printf("Pa: ");
//    PrintPolynomial(Pa);
//    printf("Pb: ");
//    PrintPolynomial(Pb);  // 应该输出0，因为Pb已被销毁
//
//    DestroyPolynomial(&Pa);
//    return 0;
//}